Manacher's Algorithm Demo - Longest Palindromic Substring

📝 Problem Statement & Input Strings

Problem Statement:

Aria is working on a text analysis tool... Her task is to identify the **longest palindromic substring** in each of the feedback messages collected. If there are multiple palindromic substrings of the same maximum length, she prefers the one that appears first in the message (i.e., the one with the **smallest starting index**).

**Input:** Two input strings (corresponding to two test cases).

**Output:** The longest palindromic substring for each string on a separate line.

Example: Input 'abaca', 'abbcd'. Output 'aba', 'bb'.

Input Strings

Input String 1 (S1):

Input String 2 (S2):

Final Output (Result for the two input strings)

Result for String 1:

?

Result for String 2:

?

*Note: Use the "Load S1 into Step-by-Step Demo" button to see the algorithm visualization on the third slide.*

💡 Manacher's Core Logic (Linear Time Optimization)

The P Array and Key Variables

**P[i]:** The palindromic radius centered at $T[i]$. $P[i]-1$ is the length of the palindrome in the original string $S$.
**Center (C):** The index in $T$ corresponding to the center of the largest palindrome found *so far*.
**Right Boundary (R):** The rightmost boundary of this palindrome ($R = C + P[C]$).

Symmetry Optimization:

For the current index $i$, calculate its **mirror index** $i' = 2 \cdot C - i$.
**Initial Guess:** If $i$ is within the current $R$ boundary ($i < R$), we can set an initial minimum value for $P[i]$ based on symmetry: $$\text{Initial } P[i] = \min(P[i'], R - i)$$
If $i$ is outside $R$ or if $P[i']$ extends past $R$, we start with $P[i] = 1$.
**Expansion:** We then attempt to expand the palindrome outwards from this initial radius: $\text{while } T[i+P[i]] == T[i-P[i]]: P[i]++$.
**Update C and R:** If the new palindrome centered at $i$ extends past $R$ ($i + P[i] > R$), we update the center $C = i$ and the boundary $R = i + P[i]$.

🎬 Step-by-Step Palindromic Radii Calculation (Current String: ?)

Load a string from the first slide to begin the visualization.

Transformed String ($T$) and P Array

Indices (i)

String ($T$)

P Array (Radii P[i])

**Current:** Index $i$=?, Center $C$=?, Right Boundary $R$=?, Mirror $i'$=?